#include <iostream>
#include <vector>
using namespace std;

class TreeAncestor {
	int cnt = 1;
	int power = 0;
	vector<int> head, next, to;
	vector<int> deep;
	vector<vector<int>> stjump;
	int log2(int n)
	{
		int ans = 0;
		while ((1 << ans) <= (n >> 1)) {
			ans++;
		}
		return ans;
	}

	void dfs(int u, int p)
	{
		if (u == 0) {
			deep[u] = 1;
		} else {
			deep[u] = deep[p] + 1;
		}

		stjump[u][0] = p;
		for (int i = 1; i <= power; i++) {
			stjump[u][i] = stjump[stjump[u][i - 1]][i - 1];
		}

		for (int e = head[u], v = 0; e; e = next[e]) {
			v = to[e];
			dfs(v, u);
		}
	}

    public:
	TreeAncestor(int n, vector<int> &parent) : head(n, 0), next(n, 0), to(n, 0), deep(n, 0), power(log2(n)), stjump(n, vector<int>(power + 1, 0))
	{
		for (int i = 1, u = 0, v = 0; i < parent.size(); i++) {
			u = parent[i], v = i;
			next[cnt] = head[u];
			head[u] = cnt;
			to[cnt++] = v;
		}
		dfs(0, 0);
	}

	int getKthAncestor2(int node, int k)
	{
		if (deep[node] <= k) {
			return -1;
		}

		int aim = deep[node] - k;
		for (int p = log2(k); p >= 0; p--) {
			if (k >= (1 << p)) {
				k -= 1 << p;
				node = stjump[node][p];
			}
		}
		// for(int p = log2(k); p >= 0; p--){
		//         if(deep[stjump[node][p]] >= aim){
		//                 node = stjump[node][p];
		//         }
		// }
		return node;
	}

        int getKthAncestor(int node, int k)
	{
                if(deep[node] <= k){
                        return -1;
                }

                int p = 0;
                while(k){
                        if(k & 1){
                                node = stjump[node][p];
                        }
                        p++;
                        k >>= 1;
                }
                return node;
        }
};

int main()
{
	vector<int> parent = { -1, 0, 0, 1, 2, 0, 1, 3, 6, 1 };
	int n = 10;
	TreeAncestor sttree(n, parent);
	cout << sttree.getKthAncestor(7, 3) << endl;
	return 0;
}